1. Technical Field
The invention relates to data compression methods in a computer environment. More particularly, the invention relates to real-time fast loss-less video compression and decompression using video frame preprocessing.
2. Description of the Prior Art
Video data is typically encoded in large blocks of memory. Even a single video frame of, for example, a size of 1K×1K can require megabytes to describe it. Video data requires large amounts of memory to store and high communication bandwidths to transfer. It therefore is highly advantageous to compress video data. However, some compression methods lose information in the process.
Some applications can tolerate various degrees of loss, but still others require loss-less compression.
The typical loss-less video data compression methods use differential pulse code modulation (DPCM). A current pixel value is replaced by the difference between it and the previous pixel. Since pixel values change rather slowly along scan lines, the difference values will near zero, making compression algorithms particularly effective. However, many times, the slow change between pixel values occurs in vertical or diagonal bands. Prior art methods that can only take advantage of horizontal bands in the image are compromised.
Huffman coding can be used to compress real-time video data. A Huffman-tree is built and the tree is used to recode the data. The basic idea is that frequently occurring video codes are replaced by a Huffman code that requires fewer bits. Occasional video codes that occur infrequently are described with Huffman codes that require more bits than the video code itself. In spite of this, the combination of Huffman codes does result in an overall gain in compression.
A conventional approach is to compute the Huffman-tree once. This is regardless of any real difference resulting from the previous tree and regardless of available processing time to handle the job at that instant. The computational time required to compute the Huffman-tree can equal that needed to run the compression for one image with that tree.
It would be advantageous to provide a fast loss less image compression system based on neighborhood comparisons that provides fast pre-processing of images. It would further be advantageous to provide a fast loss less image compression system based on neighborhood comparisons that speeds up Huffman coding and the compression of video images.